package com.zh.note.leetcode.dp;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 139. 单词拆分
 */
public class LC_139_wordBreak {
    /**
     * 求组合数，先遍历物品后遍历背包
     * 求排列数，先遍历背包后遍历物品
     */

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) { // 遍历背包
            for (int j = 0; j < i && !dp[i]; j++) { // 遍历物品
                String word = s.substring(j, i);
                if (set.contains(word) && dp[j]) {
                    dp[i] = true;
                }
            }
        }

        return dp[s.length()];
    }
}
